package week02

import "math"

// 98. 验证二叉搜索树
// https://leetcode-cn.com/problems/validate-binary-search-tree/submissions/

// 1、所有子树都为二叉搜索树
// 2、左子树的最大值 < 根的值
// 3、右子树的最小值 > 根的值

func isValidBST(root *TreeNode) bool {
	isValid, _, _ := isValidBST2(root)
	return isValid
}

// isValid, min, max
func isValidBST2(root *TreeNode) (bool, int64, int64) {
	if root == nil {
		return true, math.MaxInt64, math.MinInt64
	}
	isValidL, minL, maxL := isValidBST2(root.Left)
	// 左子树不是二叉搜索树，直接退出，没必要遍历右子树了
	if !isValidL || maxL >= int64(root.Val) {
		return false, 0, 0
	}
	isValidR, minR, maxR := isValidBST2(root.Right)
	var isValid = isValidR && int64(root.Val) < minR
	var min1 = min(int64(root.Val), min(minL, minR))
	var max1 = max(int64(root.Val), max(maxL, maxR))
	return isValid, min1, max1
}

func max(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func min(x, y int64) int64 {
	if x > y {
		return y
	}
	return x
}

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}
